#include <stdlib.h>
#include <stdio.h>
#include <limits.h>
#include <math.h>
#include <queue.h>
#include <vector.h>

#include "HPDB.h"
#include "HGenerica.h"
#include "Excepcion.h"
#include "CasilleroIDA.h"



int fact(int n){
    int r = 1;
    for(;n>0; r*=n--);
    return r;
}


int factDes(int n, int d){
    int r = 1;
    for(;d--; r*=n--);
    return r;
}


HPDB::HPDB(const char *Conjuntos, int dimenciones) {

    int i, l;
    TablaHash **tablasAyd, **biyConjTabla;

    l = dimenciones * dimenciones;

    numeroDeTablas = 0;
    //Arreglo de tablas (adyacentes).
    tablasAyd = (TablaHash **) malloc(l * sizeof (TablaHash *));
    //Arreglo de correspondencia entre numero y tabla.
    biyConjTabla = (TablaHash **) malloc(l * sizeof (TablaHash *));
    for (i = 0; i < l; i++) biyConjTabla[i] = NULL;

    //Generando Conjuntos de Abstraccion:
    for (i = 0; i < l; i++) {
        TablaHash *tabla;

        if (Conjuntos[i] >= l || Conjuntos < 0)
            throw new Excepcion("El numero de Conjunto debe estar en [0, dimenciones^2) en HPDB::HPDB(const char *Conjuntos, int dimenciones).");

        tabla = biyConjTabla[Conjuntos[i]];

        if (!tabla) { //Se crea una nueva tabla:
            int j;
            tablasAyd[numeroDeTablas] = new TablaHash();
            tablasAyd[numeroDeTablas]->mascara = (char *) malloc(sizeof (char) *l);
            
            //Se pone toda la tabla con abstraida:
            tablasAyd[numeroDeTablas]->concretas = 0;
            for (j = 0; j < l; tablasAyd[numeroDeTablas]->mascara[j++] = 0);
            
            
            //Se asigna la biyeccion;
            biyConjTabla[Conjuntos[i]] = tablasAyd[numeroDeTablas];
            tabla = tablasAyd[numeroDeTablas];
            numeroDeTablas++;
        }

        //Se le quita la abstraccion a la casilla i:
        tabla->mascara[i] = 1;
        tabla->concretas++;
    }

    //Inicializando tablas de Abstraccion:
    tablas = (TablaHash **) malloc(numeroDeTablas * sizeof (TablaHash *));
    for (i = 0; i < numeroDeTablas; i++) {
        tablas[i] = tablasAyd[i];
        
        if(tablas[i]->mascara[0]==0){
            tablas[i]->mascara[0] = 1;
            tablas[i]->concretas++;
        }
        
        tablas[i]->largo = factDes(l , tablas[i]->concretas);
        //Asignando memoria al arreglo de valores:
        tablas[i]->valores = (unsigned char *) malloc(sizeof (unsigned char) * tablas[i]->largo);
    }

    free(biyConjTabla);
    free(tablasAyd);

    conjuntos = (char *) malloc(sizeof (char) * l);
    for (i = 0; i < l; conjuntos[i] = Conjuntos[i], i++)
        this->dimenciones = dimenciones;

    for (i = 0; i < numeroDeTablas; i++)
        dijistra_PDB(tablas[i]);
}

HPDB::~HPDB() {
    int i;

    if (conjuntos) free(conjuntos);


    if (tablas)
        for (i = 0; i < numeroDeTablas; delete tablas[i++]);

    free(tablas);

}

const char *HPDB::Conjuntos() const {
    return conjuntos;
}

void HPDB::print() const {
    int i, j;
    const int l = dimenciones * dimenciones;
    for (i = 0; i < numeroDeTablas; i++) {
        printf("\nTabla %d:\n", i);
        for (j = 0; j < l; j++) {
            printf("%d ", tablas[i]->mascara[j] * j);
            if (j % dimenciones == dimenciones - 1)
                printf("\n");
        }
        printf("\n");
    }
}

int HPDB::h(CNodo* estado){
    int i, val = 0;
    for (i = 0; i < numeroDeTablas; i++){
        int hash = HashPerfecto(estado, tablas[i]->mascara, tablas[i]->concretas);
        val += tablas[i]->valores[hash];
        
    }
    return val;
}



// <editor-fold defaultstate="collapsed" desc="Privados">

class CNodoH {
public:
    char h;
    CNodo *cNodo;

    CNodoH(Casillero *casillero, CNodo::Operador accion, CNodo *enlace) {
        cNodo = new CNodo(casillero, accion, enlace);
        h = 0;
    }

    CNodoH(CNodo *cNodo) {
        this->cNodo = cNodo;
        h = 0;
    }

    CNodoH * GenerarSucesorH(CNodo::Operador oper) const {
        CNodo *n = cNodo->GenerarSucesor(oper);

        if (n) return new CNodoH(n);

        return NULL;
    }
    
    ~CNodoH(){
        delete cNodo;
    }
};

class arrCasComp {
    bool reverse;
public:

    arrCasComp(const bool& revparam = false) {
        reverse = revparam;
    }

    bool operator() (const CNodoH *lhs, const CNodoH *rhs) const {
        if (reverse) return lhs->h > rhs->h;
        else return lhs->h < rhs->h;
    }
};

typedef priority_queue<CNodoH *, vector<CNodoH *>, arrCasComp> Cola;

int HPDB::HashPerfecto(const CNodo *s, const char *abst, int conc) const {
    int rank = 0;

    int l = dimenciones * dimenciones;
    const Casillero *cas = s ->Casillas();

    int k = (int) ceil(log2((double) conc));
    int sizeTree = (1 << (1 + k)) - 1; // 2^(1+k) - 1
    int i, j;

    int Tree[sizeTree];
    int *Root = Tree + 1;
    
    for (i = 0; i < sizeTree; i++) Tree[i] = 0;
    
    char Map[628];
    int  d[628];
	
    //Setting the perm to Tree map:
    for(i = 0, j = 0; i < l; i++)
        if(abst[i]) Map[i] = j++;

    int p2toK = 1 << k; // 2^k

    for (i = 0; i < l; i++) {
        int val = cas->Info(i);
	if(abst[val]) {
            int ctr = i;
            int node = p2toK + Map[val];

            for (j = 0; j < k; j++) {
                if (node % 2)
                    ctr -= Tree[ (node >> 1) << 1 ];
                Tree[node]++;
                node >>= 1; // node / 2
            }

            *Root++;

            d[Map[val]] = ctr;
        }
    }
	
    int c = l;
    for(i = 0; i < conc; i++)
	rank = rank * (c--) + d[i];

    return rank;


}

void HPDB::dijistra_PDB(TablaHash *tabla) {
    int i, l, *cas;
    CNodoH *s0;

    l = dimenciones * dimenciones;

    //Tablero inicial:
    cas = (int *) malloc(sizeof (int) * l);
    for (i = 0; i < l; cas[i] = i, i++);

    s0 = new CNodoH(new CasilleroIDA(cas, dimenciones, 0), (CNodo::Operador) - 1, NULL);

    //Inicializo la tabla H(s) = inf;
    for (i = 0; i < tabla->largo; tabla->valores[i++] = UCHAR_MAX);
    
    

    //Cola de prioridades:
    Cola *q = new Cola(arrCasComp(true));

    q->push(s0);
    tabla->valores[HashPerfecto(s0->cNodo, tabla->mascara, tabla->concretas)] = 0;

    while (!q->empty()) {
        CNodoH *s = q->top();
        q->pop();

        for (i = 0; i < 4; i++) {
            CNodoH *s1 = s->GenerarSucesorH(CNodo::operadores[i]);
            
            if (s1) {
                int hash = HashPerfecto(s1->cNodo, tabla->mascara, tabla->concretas);
                
                        
                if (tabla->valores[hash] == UCHAR_MAX) {
                    
                    s1->h = s->h + 1;
                    tabla->valores[hash] = s1->h;
                    q->push(s1);
                    
                } else delete s1;
            }

        }
        
        delete s;
    }
}

HPDB::TablaHash::~TablaHash() {
    if (valores) {
        void *memoria = valores;
        free(memoria);
    }
}

// </editor-fold>
